package algorithm.leetcode.medium;

/*
 一条包含字母 A-Z 的消息通过以下方式进行了编码：
    'A' -> 1
    'B' -> 2
    ...
    'Z' -> 26
 给定一个只包含数字的非空字符串，请计算解码方法的总数。
 */

/**
 * @author jack.wu
 * @version 1.0
 * @date 2020/11/23
 */
public class Question91 {

    public static void main(String[] args) {
        Question91 question = new Question91();
        int numDecodings = question.numDecodings("226");
        System.out.println(numDecodings);
    }

    /**
     * 思路：
     * 如果 i-1 位与 i 位能组成 10 - 26之间的数字
     * 1、如果组成的数是 10 | 20  dp[i] = dp[i - 2];
     * 2、如果组成的数是 11 - 26(不含20) dp[i] = dp[i - 1] + dp[i - 2];
     * 如果 i-1 位与 i 位不能组成 10 - 26之间的数字
     * 1、如果第 i 位是 0 不能编码 return 0;
     * 2、如果第 i 位不是 0 dp[i] = dp[i-1];
     *
     * @param s 加密串
     * @return 解码方法次数
     */
    public int numDecodings(String s) {
        int len = s.length();
        if (len == 0) {
            return 0;
        }
        int[] dp = new int[len];
        char[] chars = s.toCharArray();
        if (chars[0] == '0') {
            return 0;
        }
        // 如果上面没有返回 这里一定是有一次
        dp[0] = 1;
        char ch;
        int num;
        for (int i = 1; i < len; i++) {
            ch = chars[i];
            if (ch != '0') {
                // 这里如果不是 0 先用上次的
                dp[i] = dp[i - 1];
            }
            // 前一项和当前项能不能组成 10 - 26
            num = 10 * (chars[i - 1] - '0') + (ch - '0');
            if (num >= 10 && num <= 26) {
                if (i == 1) {
                    dp[i]++;
                } else {
                    dp[i] += dp[i - 2];
                }
            }
        }
        return dp[len - 1];
    }

}
